package com.lxl.shell;

import java.util.Arrays;

/**
 * @Classname ShellSort
 * @Description 希尔排序 （直接插入排序的优化）
 * @Date 2021/8/12 17:15
 * @Created by LXLDEMO
 */
public class ShellSort {
    public static void main(String[] args) {
        // 测试用例
        int arr[] = {2,4,3,1,6,5};

        // 希尔排序测试
        shellSort(arr,arr.length);

    }

    /**
     * 希尔排序
     * 插入排序的优化 用的少 代码可读性差
     * 重点：选择增量 初始值为 n/2 减少了移动的次序和比较的次数
     * 时间复杂度(O(n^1.3))
     * @param arr
     * @param len
     */
    public static void shellSort(int[] arr,int len){
        System.out.println("初始数据 " + Arrays.toString(arr));
        int out=1; // 用于统计外层循环次数
        for (int d = len/2;d>0;d/=2){
            System.out.println("\n\n第"+(out++) +"次分组 "+ "分组步长："+d);
            int in = 1;//用于统计内层循环
            for (int i=d;i<len;i++){
                System.out.println("第"+in +"轮");
                int temp = arr[i]; // 即某个组的第二个元素
                int j;
                // 一轮for循环进行的是多组排序
                for (j=i-d;j>=0&&temp<=arr[j];j-=d){
                    arr[j+d] =arr[j];
                }
                arr[j+d]=temp;
                System.out.println("第"+(in++) +"轮结果 "+Arrays.toString(arr));
            }
        }
    }
}
